ব্যাকট্র্যাকিং (Backtracking) হল একটি সমস্যা সমাধানের কৌশল যা পরপর সিদ্ধান্ত নেওয়ার মাধ্যমে কাজ করে। এই পদ্ধতিতে, একটি সম্ভাব্য সমাধান গঠনের সময় অগ্রসর হয়, এবং যদি কোন পয়েন্টে সেই সমাধানটি ভুল বা অযোগ্য হয়, তাহলে পেছনে ফিরে গিয়ে অন্য সম্ভাবনার দিকে অগ্রসর হয়। ব্যাকট্র্যাকিং সাধারণত সমস্যাগুলির ক্ষেত্রে ব্যবহৃত হয় যেখানে সিদ্ধান্ত নেওয়ার সময় বিভিন্ন বিকল্প থাকে এবং সেই বিকল্পগুলির মধ্যে থেকে সঠিক সমাধান খুঁজে বের করতে হয়।
ব্যাকট্র্যাকিং এর মূল ধারণা
ডিসিশন ট্রি: ব্যাকট্র্যাকিং কৌশলে সমস্যার সমাধানের জন্য একটি ডিসিশন ট্রি তৈরি করা হয়। প্রতিটি নোডে একটি সিদ্ধান্ত নির্দেশ করে এবং প্রতিটি শাখা সম্ভাব্য পরবর্তী সিদ্ধান্তকে নির্দেশ করে।
প্রসঙ্গ হ্রাস: যখন কোন সিদ্ধান্তের ভিত্তিতে সঠিক সমাধান পাওয়া যায় না, তখন অগ্রসর হওয়ার পরিবর্তে পূর্ববর্তী স্তরে ফিরে আসা হয় এবং নতুন সম্ভাবনার দিকে অগ্রসর হওয়া হয়।
সমস্যার সমাধান: ব্যাকট্র্যাকিং অ্যালগরিদমের উদ্দেশ্য হলো সম্ভাব্য সমাধানগুলি পরীক্ষা করা এবং প্রথমে সঠিক সমাধান পাওয়া।
ব্যাকট্র্যাকিং কৌশল
ব্যাকট্র্যাকিংয়ের কৌশল সাধারণত তিনটি ধাপে কাজ করে:
- নির্বাচন: কোন বিকল্পগুলি নির্বাচন করতে হবে এবং সেই অনুযায়ী সিদ্ধান্ত নিতে হবে।
- জারি রাখা: নির্বাচিত বিকল্পের ভিত্তিতে পরবর্তী স্তরে অগ্রসর হওয়া।
- বাক্সে ফিরে আসা: যদি কোন সমাধান পাওয়া না যায়, তবে পূর্ববর্তী স্তরে ফিরে আসা এবং নতুন বিকল্প নির্বাচন করা।
উদাহরণ
১. এন-কুইন সমস্যা (N-Queens Problem)
ন-রানী সমস্যা হল একটি ক্লাসিক্যাল ব্যাকট্র্যাকিং সমস্যা যেখানে n সংখ্যক রানীকে n × n এর একটি চৌকাটিতে এমনভাবে স্থাপন করতে হয় যাতে কোন রানী অন্য রানীকে আক্রমণ করতে না পারে।
def is_safe(board, row, col, n):
# একই কলামে আরেক রানী আছে কি না পরীক্ষা করুন
for i in range(row):
if board[i][col] == 1:
return False
# ডায়াগোনাল পরীক্ষা করুন
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
for i, j in zip(range(row, -1, -1), range(col, n)):
if board[i][j] == 1:
return False
return True
def solve_n_queens_util(board, row, n):
if row >= n:
return True
for col in range(n):
if is_safe(board, row, col, n):
board[row][col] = 1 # রানী রাখুন
if solve_n_queens_util(board, row + 1, n):
return True # পরবর্তী রানীর অবস্থান
board[row][col] = 0 # ব্যাকট্র্যাকিং
return False
def solve_n_queens(n):
board = [[0] * n for _ in range(n)]
if not solve_n_queens_util(board, 0, n):
print("Solution does not exist")
return False
else:
for row in board:
print(row)
return True
# ব্যবহার
n = 4
solve_n_queens(n)
২. পারমুটেশন (Permutation)
ব্যাকট্র্যাকিং কৌশল ব্যবহার করে একটি সেটের সমস্ত পারমুটেশন বের করা।
def backtrack(path, options):
if not options:
print(path)
return
for i in range(len(options)):
backtrack(path + [options[i]], options[:i] + options[i+1:])
# ব্যবহার
options = [1, 2, 3]
backtrack([], options) # সকল পারমুটেশন প্রিন্ট করুন
উপসংহার
ব্যাকট্র্যাকিং একটি শক্তিশালী সমস্যা সমাধানের কৌশল যা বিভিন্ন সমস্যা, যেমন গাণিতিক সমস্যা, পাজল সমাধান, এবং সর্বাধিক সমস্যা সমাধানে কার্যকরী। এটি সম্ভাব্য সমাধানগুলি পরীক্ষা করে এবং কার্যকরভাবে সমস্যা সমাধানে একটি কাঠামো প্রদান করে। ব্যাকট্র্যাকিং কৌশলটি কম্পিউটার বিজ্ঞানে এবং গাণিতিক অ্যালগরিদমে ব্যাপকভাবে ব্যবহৃত হয়।
